home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / srtkit11.zip / COMBSORT.PAS < prev    next >
Pascal/Delphi Source File  |  1992-03-07  |  4KB  |  113 lines
  1. (******************************************************************************
  2. *                                  combSort                                   *
  3. * a combined sort is a mergsort that uses an internal quicksort in the        *
  4. * splitFile phase to create long telems.                                      *
  5. ******************************************************************************)
  6. unit combSort;
  7.  
  8. {$R-}
  9.  
  10. interface
  11.  
  12. uses
  13.    mergSort
  14.    ,quickSrt
  15.    ;
  16.  
  17. type
  18.    combinedSortPtr = ^ combinedSort;
  19.    combinedSort = object(mergeSort)
  20.       qs : quickSortPtr;
  21.       ap : arrayOfPointersPtr;
  22.       
  23.       constructor init( fn : string;   { file name }
  24.                         bs : word;     { block size }
  25.                         tp : string;   { temp path }
  26.                         on : string;   { outfile name }
  27.                         q  : quickSortPtr { how to do the internal sort }
  28.                         );
  29.       function    splitFile : longInt; virtual;
  30.  
  31.    end; { combinedSort object definition }
  32.  
  33. implementation
  34.  
  35. (******************************************************************************
  36. *                              combinedSort.init                              *
  37. ******************************************************************************)
  38. constructor combinedSort.init;
  39. begin
  40.    mergeSort.init(fn, bs, tp, on);
  41.    qs := q;
  42. end; {combinedSort.init}
  43.  
  44. (******************************************************************************
  45. *                           combinedSort.splitFile                            *
  46. ******************************************************************************)
  47. function combinedSort.splitFile;
  48. var
  49.    initialSize   : longInt;
  50.    { maximum number of sort records that can be performed by an internal sort }
  51.    recordsToSort : longInt; 
  52.    { number of records to sort in a specific phase of the internal sort }
  53.    reachedEOF    : boolean;
  54.    writeTo1      : boolean; { trigger, when true write to t1, else write to t2 }
  55.    i             : longint; { used to count total number of records in file }
  56.    j             : longint; 
  57.    pp            : pointer;
  58. begin                 
  59.    writeTo1 := true;
  60.    i := 0;
  61.    reachedEOF := false;
  62.    assign(t1, tempPath + 'mrgsrtt1.$$$');
  63.    rewrite(t1, blokSize);
  64.    if (ioResult <> 0) then
  65.       reachedEOF := true;
  66.    assign(t2, tempPath + 'mrgsrtt2.$$$');
  67.    rewrite(t2, blokSize);
  68.    if (ioResult <> 0) then
  69.       reachedEOF := true;
  70.    initialSize := maxAvail div (blokSize + sizeOf(pointer)) - 1; 
  71.    { one used internally by quicksort .. }
  72.    getMem(ap, initialSize * sizeOf(pointer)); 
  73.    { ap points to start of the array of pointers to block data }
  74.    while (not reachedEOF) do begin
  75.       recordsToSort := 0; { number of records to pass for internal sort .. }
  76.       while ((recordsToSort < initialSize) and (not eof(mergFile))) do begin
  77.          inc(recordsToSort);
  78.          getMem(block1, blokSize);
  79.          blockRead(mergFile, block1^, 1);
  80.          ap^[recordsToSort] := block1;
  81.       end; { read more blocks to be sorted in this phase }
  82.       if (eof(mergFile)) then
  83.          reachedEOF := true;
  84.       if (recordsToSort <> 0) then begin
  85.          qs^.numberOfElements := recordsToSort;
  86.          qs^.ptrArray := ap; { set parameters for this phase of the internal sort }
  87.          qs^.doYourJob;
  88.          for j := 1 to recordsToSort do begin
  89.             pp := ap^[j];
  90.             if (writeTo1) then 
  91.                blockWrite(t1, pp^, 1)
  92.             else
  93.                blockWrite(t2, pp^, 1);
  94.             freemem(pp, blokSize);
  95.          end; { writing the telem to the file }
  96.          writeTo1 := not writeTo1;
  97.          i := i + recordsToSort;
  98.       end; { there were records to sort .. }
  99.    end; { while .. for read }
  100.    freemem(ap, initialSize * sizeof(pointer));
  101.    splitFile := i; { we return the number of records in the file .. }
  102.    close(mergFile);
  103.    close(t1);
  104.    close(t2);
  105.    telem := initialSize; { this is the catch, here we have an initial size .. }
  106. end; {combinedSort.splitFile}
  107.  
  108. (******************************************************************************
  109. *                                    MAIN                                     *
  110. ******************************************************************************)
  111. end.
  112. 
  113.